package com.wish.datastructure;


/**
 * Created by suliucheng on 2021/4/6 9:44
 * Directions:
 * 求单链表中有效节点的个数
 * 查找单链表中倒数第 k 个节点(新浪面试题)
 * 单链表的反转（腾讯面试题）
 */
public class SingleLinkedListInterviewDemo01 {
    public static void main(String[] args) {
        LinkedListDemo listDemo = new LinkedListDemo();
        listDemo.add(new Node(1, "苏刘成"));
        listDemo.add(new Node(2, "吴炬"));
        listDemo.add(new Node(3, "马化腾"));
        listDemo.add(new Node(4, "周杰伦"));
        listDemo.list();
        System.out.println("该链表的有效节点个数为：" + listDemo.countNodes());

        int k = 2;
        Node node = listDemo.getTheLastKNode(k);
        System.out.println("(新浪面试题)倒数第" + k + "个节点是：\n" + node);

        System.out.println("(百度面试题)链表倒序遍历：");
        listDemo.reverseList();

        listDemo.reverse(listDemo.getHead());
        listDemo.list();


    }
}

/**
 * 链表类管理节点类
 * add
 * delete
 * modify
 * list
 */
class LinkedListDemo {
    //头结点
    private Node head = new Node(0, "head");

    public Node getHead() {
        return head;
    }

    /**
     * 添加新的节点到链表的尾部
     *
     * @param node
     */
    public void add(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 遍历链表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }

    }

    /**
     * 获取链表中有效节点的个数
     *
     * @return 有效节点个数
     */
    public Integer countNodes() {
        int counts = 0;
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            counts++;
        }
        return counts;
    }

    /**
     * 获取链表中倒数第k个节点的信息
     *
     * @param k 序号
     * @return 节点
     */
    public Node getTheLastKNode(Integer k) {
        int counts = 0;
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            counts++;
        }
        return getPreNode((counts - k) + 1);
    }

    /**
     * 获取从前往后数第i个有效节点
     *
     * @param i 序号
     * @return 节点
     */
    private Node getPreNode(int i) {
        int counts = 0;
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            counts++;
            if (counts == i) {
                return temp;
            }
        }
        throw new RuntimeException("参数异常：k");
    }

    /**
     * 倒序遍历链表
     */
    public void reverseList() {
        if (head.next == null) {
            throw new RuntimeException("方法异常：链表为空");
        }
        Integer i = countNodes();
        while (i > 0) {
            if (i == 0) {
                break;
            }
            System.out.println(getPreNode(i));
            i--;
        }

    }

    /**
     * 获取链表的反转
     */
    public void reverse(Node head) {
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义一个辅助的指针，帮我们遍历原来的链表
        Node current = head.next;
        //指向当前节点的下一个节点
        Node next = null;
        Node reverseHead = new Node(0, "newNode");
        //遍历原来的链表，每遍历一个节点，就将其去除，并放在新的链表reverseHead最前端
        while (current != null) {
            next = current.next;
            current.next = reverseHead.next;
            current = next;
        }
        //将head.next指向reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }
}

/**
 * 节点类
 */
class Node {
    /**
     * 头信息
     */
    Integer number;
    /**
     * 数据体信息
     */
    String name;
    /**
     * 尾部指针
     */
    Node next;

    public Node(Integer number, String name) {
        this.number = number;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "number=" + number +
                ", name='" + name + '\'' +
                '}';
    }
}